
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct ListNode 
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#if 0
class Solution
{
    int idx = 0;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        idx = postorder.size() - 1;
        return createTree(inorder, postorder, 0, inorder.size() - 1);
    }

    int storeWater(vector<int>& bucket, vector<int>& vat)
    {
        int maxvat = *(max_element(vat.begin(), vat.end()));
        if (0 == maxvat)
            return 0;

        int res = INT_MAX, n = vat.size();
        for (int cnt = 1, uplevel = 0; cnt <= maxvat && cnt < res; ++cnt)
        {
            uplevel = 0;
            for (int i = 0; i < n; ++i)
            {
                uplevel += max(0, (vat[i] + cnt - 1) / cnt - bucket[i]);
            }

            res = min(res, cnt + uplevel);
        }

        return res;
    }
private:
    TreeNode* createTree(const vector<int>& inorder, const vector<int>& postorder, int lf, int rg)
    {
        if (lf > rg)
            return nullptr;

        int pos = 0;
        for (int i = lf; i <= rg; ++i)
        {
            if (inorder[i] == postorder[idx])
            {
                pos = i;
                break;
            }
        }

        TreeNode* root = new TreeNode(inorder[pos]);
        --idx;
        root->right = createTree(inorder, postorder, pos + 1, rg);
        root->left = createTree(inorder, postorder, lf, pos - 1);

        return root;
    }
};
#endif

class Solution
{
public:
    int m = 0, n = 0;
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };

    bool exist(vector<string>& board, string word)
    {
        int flag = 0, idx = 0;
        m = board.size(), n = board[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (_exit(board, word, vis, i, j, idx))
                {
                    flag = 1;
                    break;
                }
            }
            if (flag)
                break;
        }

        return flag ? true : false;
    }

    bool _exit(const vector<string>& board, const string& word, vector<vector<bool>>& vis, int row, int col, int idx)
    {
        if (board[row][col] != word[idx])
            return false;
        if (idx + 1 == word.size())
            return true;

        vis[row][col] = true;
        for (int i = 0; i < 4; ++i)
        {
            int x = row + dx[i], y = col + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y])
            {
                if (_exit(board, word, vis, x, y, idx + 1))
                    return true;
            }
        }
        vis[row][col] = false;

        return false;
    }

    ListNode* ReverseList(ListNode* head)
    {
        ListNode* cur = head, * prev = nullptr;

        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        if (m == n)
            return head;

        int cnt = 1;
        ListNode* cur = head;
        ListNode* pprev = head, * nnext = nullptr;

        while (cnt != m)
        {
            ++cnt;
            pprev = cur;
            cur = cur->next;
        }
        nnext = cur;

        ListNode* prev = nullptr;
        while (cnt <= n)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
            ++cnt;
        }

        pprev->next = prev;
        nnext->next = cur;

        return 1 == m ? prev : head;
    }

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode dummy(-1), * tail = &dummy;
        ListNode* cur1 = pHead1, * cur2 = pHead2;

        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
        tail->next = cur1 ? cur1 : cur2;

        return dummy.next;
    }
};

void Test1()
{
    vector<string> vs{ "XYZE", "SFZS", "XDEE" };
    const string s = "EE";
    /*vector<string> vs{ "abc", "def"};
    const string s = "cf";*/

    cout << Solution().exist(vs, s) << endl;
}

int main()
{
    Test1();

    return 0;
}

#if 0
int main()
{
    int n = 0, k = 0;
    cin >> n >> k;

    int sum = 0;
    priority_queue<int> pq;
    for (int i = 0; i < n; ++i)
    {
        int tmp = 0;
        cin >> tmp;
        sum += tmp;
        if (0 == tmp % 2)
            pq.push(tmp);
    }

    int cnt = 0;
    for (int top = 0; cnt < k && pq.size();)
    {
        top = pq.top();
        pq.pop();
        top /= 2;
        sum -= top;
        if (0 == top % 2)
            pq.push(top);
        ++cnt;
    }

    return sum;
}
#endif